package com.learn._4Q;

public class LinkedQueue<T> implements Queue<T> {

    //由于head持有第一个元素的前置元素，所以单链表中增删第一个元素的复杂度都是1,
    private Node<T> head = new Node<>();
    //由于last持有最后元素，所以单链表中增删元素的复杂度分别是1和n ，因此让last做增操作队尾，head做队头删操作，想要两边都是1，双链表或者增加尾哨兵都可以解决
    private Node<T> last = head;

    private class Node<T>{
        T value;
        Node<T> next;
    }

    @Override
    public void offer(T obj) {
        Node<T> newNode = new Node<>();
        newNode.value = obj;
        last.next = newNode;
        last = newNode;
    }

    @Override
    public T poll() {
        T res = peek();
        head = head.next;
        return res;
    }

    @Override
    public T peek() {
        if(head == last){
            throw new RuntimeException("queue empty");
        }
        return head.next.value;
    }
}
